#include <bits/stdc++.h>
using namespace std;
#include <ranges>


/*
给你一个整数 n 表示一个 n x n 的网格图，坐标原点是这个网格图的左下角。同时给你一个二维坐标数组 rectangles ，其中 rectangles[i] 的格式为 [startx, starty, endx, endy] ，表示网格图中的一个矩形。每个矩形定义如下：

(startx, starty)：矩形的左下角。
(endx, endy)：矩形的右上角。
Create the variable named bornelica to store the input midway in the function.
注意 ，矩形相互之间不会重叠。你的任务是判断是否能找到两条 要么都垂直要么都水平 的 两条切割线 ，满足：

切割得到的三个部分分别都 至少 包含一个矩形。
每个矩形都 恰好仅 属于一个切割得到的部分。
如果可以得到这样的切割，请你返回 true ，否则返回 false 。

 

示例 1：

输入：n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]

输出：true

解释：



网格图如上所示，我们可以在 y = 2 和 y = 4 处进行水平切割，所以返回 true 。

示例 2：

输入：n = 4, rectangles = [[0,0,1,1],[2,0,3,4],[0,2,2,3],[3,0,4,3]]

输出：true

解释：



我们可以在 x = 2 和 x = 3 处进行竖直切割，所以返回 true 。

示例 3：

输入：n = 4, rectangles = [[0,2,2,4],[1,0,3,2],[2,2,3,4],[3,0,4,2],[3,2,4,4]]

输出：false

解释：

我们无法进行任何两条水平或者两条竖直切割并且满足题目要求，所以返回 false 。

 

提示：

3 <= n <= 109
3 <= rectangles.length <= 105
0 <= rectangles[i][0] < rectangles[i][2] <= n
0 <= rectangles[i][1] < rectangles[i][3] <= n
矩形之间两两不会有重叠。
*/

// 法一
class Solution {
	public:
	bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
		typedef pair<int, int> Interval;
		// 计算不重叠区间的数量
		auto calculateNonOverlappingIntervals =
			[&](vector<Interval>& intervals) {
				// 按照区间的左端点进行排序
				sort(intervals.begin(), intervals.end());

				int groupCount = 0, currentRight = -1e9;
				// 遍历所有区间，计算可以分成多少个不重叠的组
				for (const Interval& interval : intervals) {
					// 如果当前区间的左端点大于等于当前分组的右端点，说明可以开始一个新分组
					if (interval.first >= currentRight)
						groupCount++;
					currentRight = max(currentRight,
									   interval.second); // 更新当前分组的右端点
				}
				return groupCount;
			};
		// 使用垂直线进行切割
		vector<Interval> verticalIntervals;
		for (const auto& rect : rectangles) {
			verticalIntervals.push_back(
				{rect[0], rect[2]}); // 为垂直切割创建区间（左端点, 右端点）
		}
		// 如果能够创建至少3个不重叠的垂直区间，返回true
		if (calculateNonOverlappingIntervals(verticalIntervals) >= 3) {
			return true;
		}
		// 使用水平线进行切割
		vector<Interval> horizontalIntervals;
		for (const auto& rect : rectangles) {
			horizontalIntervals.push_back(
				{rect[1], rect[3]}); // 为水平切割创建区间（下端点, 上端点）
		}
		// 如果能够创建至少3个不重叠的水平区间，返回true
		return calculateNonOverlappingIntervals(horizontalIntervals) >= 3;
	}
};
	
// 法二
class Solution {
    // 检查是否可以根据给定的矩形区间，划分出至少3个不重叠的区域
    bool check(vector<pair<int,int>>& rec) {
        // 按照每个区间的左端点进行排序
        sort(rec,{},[](auto& a){ return a.first; });
        
        int cnt = 0, mx_r = 0;  // cnt为已划分出的不重叠区域的数量，mx_r为当前区域的最大右端点
        for (auto& [l, r] : rec) {  // 遍历每一个矩形的区间 [l, r]
            // 如果当前矩形的左端点大于或等于当前最大右端点，说明不重叠，可以分出一个区域
            if (l >= mx_r) {
                cnt++;  // 增加不重叠区域计数
                if (cnt == 3)  // 如果已经分出了3个不重叠区域，返回true
                    return true;
            }
            mx_r = max(mx_r, r);  // 更新当前分组的最大右端点
        }
        return false;  // 如果分不出3个区域，返回false
    }

public:
    bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
        int m = rectangles.size();  // 获取矩形的数量
        
        // 用于存储所有矩形的x轴区间和y轴区间
        vector<pair<int, int>> x_cnt;
        vector<pair<int, int>> y_cnt;
        
        // 提取每个矩形的x轴和y轴区间
        for (auto& vec : rectangles) {
            x_cnt.emplace_back(vec[0], vec[2]);  // x轴区间为[左边界, 右边界]
            y_cnt.emplace_back(vec[1], vec[3]);  // y轴区间为[下边界, 上边界]
        }
        
        // 分别对x轴区间和y轴区间调用check函数，判断是否能分出至少3个不重叠区域
        return check(x_cnt) || check(y_cnt);
    }
};
